We present a convex approach to probabilistic segmentation and modeling of time series data. Our approach builds upon recent advances in multivariate total variation regularization, and seeks to learn a separate set of parameters for the distribution over the observations at each time point, but with an additional penalty that encourages the parameters to remain constant over time. We propose efficient optimization methods for solving the resulting (large) optimization problems, and a two-stage procedure for estimating recurring clusters under such models, based upon kernel density estimation. Finally, we show on a number of real-world segmentation tasks, the resulting methods often perform as well or better than existing latent variable models, while being substantially easier to train. 1 Introduction In this paper, we consider the tasks of time series segmentation and modeling. Formally, suppose that we observe a sequence ofT input/output pairs, represented as (x 1,y 1), (x 2,y 2),..., (x T,y T) (1) forx t R n (which can even include functions of past outputs of the time series to capture scenarios such as autoregressive models) andy t R p (though we can also consider other possible forms of the output vector, such as categorical variables).

Compressed sensing [1], [2] is one of the most exciting topics of present-day signal processing. Signal reconstruction from its low-dimensional representation becomes a possibility, given the sparse nature of the signal and, incoherence and/or restricted isometry property (RIP) [2] of the sensing/measurement process. In this regard, a number of approaches can be used, e.g., basis pursuit (BP) [3], least absolute shrinkage and selection operator (LASSO) [4] and greedy algorithms [5]. In order to exploit the structure of the signal being sensed, a number of variants of LASSO have become popular, e.g., group LASSO (G-LASSO) [6], sparse group LASSO (SG-LASSO) [7] and fused LASSO (F-LASSO) [8], etc. In this letter we propose new LASSO formulations to handle block sparse smooth signals.

Finding the place (or time) where most or all of a set of one-dimensional signals (or profiles) jointly change in some specific way is an important question in several fields. A common situation is when we want to find change-points in a multidimensional signal, e.g., in audio and image processing [1, 2], to detect intrusion in computer networks [3, 4], or in financial and economics time series analysis [5]. Another important situation is when we are confronted with several 1-dimensional signals which we believe share common changepoints, e.g., genomic profiles of a set of patients. The latter application is increasingly important in biology and medicine, in particular for the detection of copy-number variation along the genome [6], or the analysis of microarray and genetic linkage studies [7]. The common thread in biological applications is the search for data patterns shared by a set of individuals, such as cancer patients, at precise places on the genome; in particular, sudden changes in measured values. As opposed to the segmentation of multidimensional signals such as speech, where the dimension is fixed and collecting more data means having longer profiles, the length of signals in genomic studies (i.e., the number of probes measured along the genome) is fixed for a given technology while the number of signals (i.e., the number of individuals) can increase when we collect data about more patients. From a statistical point of view, it is therefore of interest to develop methods that identify multiple change-points shared by several signals that can benefit from increasing the number of signals. There exists a vast literature on the change-point detection problem [8, 9]. Here we focus on computationally efficient methods to segment a multidimensional signal by approximating it with a piecewiseconstant one, using quadratic error criteria.